#include "deploy.h"
#include <stdio.h>

int nodeNum, linkNum, consumeNum, costServer;
struct Node nodeInfo[MAX_NODE];
struct Node nodeMap[MAX_NODE];
int consBand[MAX_CONS];
int consNode[MAX_CONS];
std::map<int, struct Consume*> csMap;
std::vector<struct Route*> ansVec, lastAns, ansBack;
int totalCost = 999999999;
int G[MAX_NODE][MAX_NODE];
int pre[MAX_NODE];
float sRatio[MAX_NODE];
bool serverVis[MAX_NODE];

void init()
{
        for(int i = 0; i < MAX_NODE; ++i)
        {
                nodeMap[i].id = i;
                nodeMap[i].count = 0;
                nodeMap[i].links.clear();
                nodeMap[i].aspect = 0;
                nodeMap[i].score = 0;
                nodeMap[i].isConsume = 0;

                nodeInfo[i].id = i;
                nodeInfo[i].count = 0;
                nodeInfo[i].links.clear();
                nodeInfo[i].aspect = 0;
                nodeInfo[i].score = 0;
                nodeInfo[i].isConsume = 0;

                sRatio[i] = 1.0;
        }
        memset(serverVis, 0, sizeof(serverVis));
        //csMap.clear();
}

void get_number(char *line, int *tmp, int len)
{
	int it, va;
	it = 0;
	for(int i = 0; i < len; ++i)
	{
		va = 0;
		while(line[it] < '0' || line[it] > '9')
		{
			++it;
		}
		while(line[it] >= '0' && line[it] <= '9')
		{
			va = va * 10 + (line[it] - '0');
			++it;
		}
		tmp[i] = va;
	}
}

void read_data(char * topo[MAX_EDGE_NUM], int line_num)
{
	int tmp[4];
	int it = 0;
	struct Link *ptrLink1, *ptrLink2;
	struct Node *ptrNode1, *ptrNode2;

        init();
        get_number(topo[it], tmp, 3);
	nodeNum = tmp[0];
	linkNum = tmp[1];
	consumeNum = tmp[2];

	it = it + 2;
	get_number(topo[it], tmp, 1);
	costServer = tmp[0];

	it = it + 2;
	for(int i = 0; i < linkNum; ++i, ++it)
	{
		get_number(topo[it], tmp, 4);

                ptrLink1 = new struct Link;
                ptrLink2 = new struct Link;

                ptrLink1->start = tmp[0];
		ptrLink1->end   = tmp[1];
		ptrLink1->band  = tmp[2];
		ptrLink1->cost  = tmp[3];

                ptrLink2->start = tmp[0];
		ptrLink2->end   = tmp[1];
		ptrLink2->band  = tmp[2];
		ptrLink2->cost  = tmp[3];
                
                ptrNode1 = nodeMap + tmp[0];
                ptrNode1->count++;
                ptrNode1->links[tmp[1]] = ptrLink1;

                ptrNode2 = nodeInfo + tmp[0];
                ptrNode2->count++;
                ptrNode2->links[tmp[1]] = ptrLink2;

                ptrLink1 = new struct Link;
                ptrLink2 = new struct Link;

                ptrLink1->start = tmp[1];
		ptrLink1->end   = tmp[0];
		ptrLink1->band  = tmp[2];
		ptrLink1->cost  = tmp[3];

                ptrLink2->start = tmp[1];
		ptrLink2->end   = tmp[0];
		ptrLink2->band  = tmp[2];
		ptrLink2->cost  = tmp[3];

                ptrNode1 = nodeMap + tmp[1];
                ptrNode1->count++;
                ptrNode1->links[tmp[0]] = ptrLink1;

                ptrNode2 = nodeInfo + tmp[1];
                ptrNode2->count++;
                ptrNode2->links[tmp[0]] = ptrLink2;
	}

        ++it;
        for(int i = 0; i < consumeNum; ++i, ++it)
        {
                get_number(topo[it], tmp, 3);
                nodeMap[tmp[1]].isConsume = 1;
                consBand[tmp[0]] = tmp[2];
                consNode[tmp[0]] = tmp[1];
        }
}

void get_info()
{
        struct Consume * ptrCS;
        std::map<int, struct Link*>::iterator  ite;
        int nodeID;

       for(int i = 0; i < nodeNum; ++i)
       {
               for(ite = nodeInfo[i].links.begin(); ite != nodeInfo[i].links.end(); ++ite)
               {
                        nodeID = ite->first;
                        ite->second->band = nodeMap[i].links[nodeID]->band;
               }
       }

       csMap.clear();
       for(int i = 0; i < consumeNum; ++i)
       {
               ptrCS = new struct Consume;
               ptrCS->id = i;
               ptrCS->nodeID = consNode[i];
               ptrCS->band = consBand[i];
               ptrCS->rBand = consBand[i];
               csMap[ptrCS->nodeID] = ptrCS;
       }
       ansVec.clear();
}

void caculate_score()
{
        std::map<int, struct Consume *>::iterator ite;
        int nodeID;
        for(int i = 0; i < nodeNum; ++i)
        {
                nodeInfo[i].score = nodeInfo[i].count;
                nodeInfo[i].aspect = 0;
        }

        for(ite = csMap.begin(); ite != csMap.end(); ++ite)
        {
                nodeID = ite->second->nodeID;
                nodeInfo[nodeID].score = nodeInfo[nodeID].score + ((ite->second->band) * 0.3);
                nodeInfo[nodeID].aspect = 1;
        }
        /*queue <struct Node*> Q;
        int nodeID;
        float score;
        struct Node *ptrNode;
        bool flag[MAX_NODE];
        std::map<int, struct Consume*>::iterator ite;
        std::map<int, struct Link*>::iterator iite;

        for(int i = 0; i < nodeNum; ++i)
        {
                nodeInfo[i].score = nodeInfo[i].count * 0.5 + nodeMap[i].score;
                nodeInfo[i].aspect = 0;
        }
        memset(flag, 0, sizeof(flag));

        for(ite = csMap.begin(); ite != csMap.end(); ++ite)
        {
                nodeID = ite->second->nodeID;
                nodeInfo[nodeID].score += (0.5 * ite->second->band);
                nodeInfo[nodeID].aspect = 1;
                flag[nodeID] = 1;
                Q.push(&nodeInfo[nodeID]);
        }

        while(!Q.empty())
        {
                ptrNode = Q.front();
                Q.pop();
                for(iite = ptrNode->links.begin(); iite != ptrNode->links.end(); ++iite)
                {
                        nodeID = iite->second->end;
                        if(!flag[nodeID])
                        {
                                nodeInfo[nodeID].aspect = ptrNode->aspect + 1;
                                Q.push(&nodeInfo[nodeID]);
                                flag[nodeID] = 1;
                        }
                        score = ptrNode->score / ((float)iite->second->cost + 1) / ((float)ptrNode->aspect + 1);
                        
                        score = score / 2;
                        nodeInfo[nodeID].score += score;
                        ptrNode->score += score;
                }
        }
        for(int i = 0; i < nodeNum; ++i)
        {
                nodeInfo[i].score = nodeInfo[i].score * sRatio[i];
        }*/
}

int find_server(int &fac)
{
        //static int pre_fac = 0;
        //static int base = 1;
        //static bool vis[MAX_NODE];
        int serverID = 0;
        int max = 0, current_score;

        for(int i = 0; i < nodeNum; ++i)
        {
                if(serverVis[i])
                {
                        continue;
                }
                current_score = 0;
                current_score += nodeInfo[i].score;
                if(current_score > max)
                {
                        serverID = i;
                        max = current_score;
                }
        }
        serverVis[serverID] = 1;
        return serverID;
}

void create_graph()
{
        std::map<int, struct Link*>::iterator ite;
        int end;
        const int MMAX = 9999999;

        for(int i = 0; i < nodeNum; ++i)
        {
                for(int j = 0; j < nodeNum; ++j)
                {
                        G[i][j] = MMAX;
                }
        }

        for(int i = 0; i < nodeNum; ++i)
        {
                for(ite = nodeInfo[i].links.begin(); ite != nodeInfo[i].links.end(); ++ite)
                {
                        if(ite->second->band > 0)
                        {
                                end = ite->second->end;
                                G[i][end] = ite->second->cost;
                        }
                }
        }
}

bool find_route(int serverID, int &endID, int &tern)
{
        bool visited[MAX_NODE];
        int min, v = 0, cu_val, rad1, rad2;
        const int MMAX = 9999999;
        int base = 1;
        static int pre_tern = tern;
        if(pre_tern != tern)
        {
                pre_tern = tern;
                base += (rand() % 10);
        }
        base = base > 100 ? 1 : base;

        if(csMap.find(serverID) != csMap.end())
        {
                endID = serverID;
                return 1;
        }

        create_graph();
        memset(pre, -1, sizeof(pre));
        memset(visited, 0, sizeof(visited));

        visited[serverID] = 1;
        for(int i = 1; i < nodeNum; ++i)
        {
                min = MMAX;
                for(int j = 0; j < nodeNum; ++j)
                {
                        cu_val = rand() % G[serverID][j];
                        cu_val += G[serverID][j];
                        if(!visited[j] && cu_val < min)
                        {
                                v = j;
                                min = cu_val;
                        }
                }
                if(csMap.find(v) != csMap.end() && G[serverID][v] * csMap[v]->rBand < costServer)
                {
                        endID = v;
                        return 1;
                }
                visited[v] = 1;

                for(int j = 0; j < nodeNum; ++j)
                {
                        rad1 = rand() % base;
                        rad2 = rand() % base;
                        if(!visited[j] && (G[serverID][v] + G[v][j] + rad1 < G[serverID][j]) + rad2)
                        {
                                G[serverID][j] = G[serverID][v] + G[v][j];
                                pre[j] = v;
                        }
                }
        }
        return 0;
}

void update_ans(int start, int end, struct Route &rt)
{
        std::map<int, struct Consume*>::iterator ite;
        std::vector<struct Route *>::iterator iite;
        int path[MAX_NODE];
        int len = 0, pos;

        if(start == end)
        {
                rt.len = 1;
                rt.band = csMap[start]->rBand;
                rt.cost = 0;
                rt.consumeID = csMap[start]->id;
                rt.serverID = start;
                rt.route_node.push_back(start);

                for(unsigned int i = 0; i < ansVec.size(); ++i)
                {
                        if(ansVec[i]->consumeID == rt.consumeID)
                        {
                                ansBack.push_back(ansVec[i]);
                                back_map(ansVec.begin() + i);
                                ansVec.erase(ansVec.begin() + i);
                                --i;
                        }
                }

                delete csMap[start];
                csMap.erase(start);
                ansVec.push_back(&rt);
                return ;
        }

        path[0] = end;
        len++;
        pos = end;
        while(pre[pos] != -1)
        {
                path[len] = pre[pos];
                len++;
                pos = pre[pos];
        }
        path[len] = start;
        len++;

        int cu, ne;
        int band, cost;
        cu = start;
        band = csMap[end]->band;
        cost = 0;
        rt.route_node.push_back(start);
        
        for(int i = len - 2; i >= 0; --i)
        {
                ne = path[i];
                band = band > nodeInfo[cu].links[ne]->band ? nodeInfo[cu].links[ne]->band : band;
                cost += nodeInfo[cu].links[ne]->cost;
                cu = ne;
                rt.route_node.push_back(ne);
        }
        rt.len = len;
        rt.band = band;
        rt.cost = cost;
        rt.consumeID = csMap[end]->id;
        rt.serverID = start;
        ansVec.push_back(&rt);
        csMap[end]->band -= band;
        if(csMap[end]->band == 0)
        {
                delete csMap[end];
                csMap.erase(end);
        }
}

void update_map()
{
        struct Route *rt;
        rt = ansVec.back();
        int cu = rt->route_node[0];
        int ne;
        for(int i = 1; i < rt->len; ++i)
        {
                ne = rt->route_node[i];
                nodeInfo[cu].links[ne]->band -= rt->band;
                cu = ne;
        }
}

void back_map(std::vector<struct Route *>::iterator ite)
{
        std::map<int, struct Consume*>::iterator csite;
        struct Route *rt = *ite;

        //恢复消费节点map
        //cout << "Resume Consume" << endl;
        int consID = consNode[rt->consumeID];
        csite = csMap.find(consID);
        if(csite != csMap.end())
        {
                csite->second->band += rt->band;
        }
        else
        {
                struct Consume *ptrCons = new struct Consume;
                ptrCons->id = rt->consumeID;
                ptrCons->nodeID = consID;
                ptrCons->band = rt->band;
                ptrCons->rBand = consBand[rt->consumeID];
                csMap[consID] = ptrCons;
        }

        //恢复路径信息
        ///cout << "Path Information" << endl;
        int count = rt->route_node.size();
        int cu = rt->route_node[0];
        int ne;
        for(int i = 1; i < count; ++i)
        {
                ne = rt->route_node[i];
                nodeInfo[cu].links[ne]->band += rt->band;
                cu = ne;
        }

        //删除之前保存的链路
        //cout << "Delete" << endl;
        //delete rt; 
        //ansVec.erase(ite);  
        //cout << "back_map Done!" << endl;   
}

void last_ans(struct Route &rt)
{
        std::map<int, struct Consume*>::iterator ite;
        std::vector<struct Route *>::iterator iite;
        ite = csMap.begin();
        rt.len = 1;
        rt.band = ite->second->rBand;
        rt.cost = 0;
        rt.consumeID = ite->second->id;
        rt.serverID = ite->second->nodeID;
        rt.route_node.push_back(ite->second->nodeID);

        //cout << rt.consumeID << "   Band: " << rt.band << endl;

        for( unsigned int i = 0; i < ansVec.size(); ++i)
        {
                if(ansVec[i]->consumeID == ite->second->id)
                {
                        back_map(ansVec.begin() + i);
                        delete ansVec[i];
                        ansVec.erase(ansVec.begin() + i);
                        i--;
                }
        }

        delete ite->second;
        csMap.erase(ite);
        ansVec.push_back(&rt);
}

void print_ans(char *filename)
{
        std::ofstream fout(filename);
        int count, rtCount;
        struct Route *rt;

        count = lastAns.size();
        fout << count << endl << endl;
        for(int i = 0; i < count; ++i)
        {
                rt = lastAns[i];
                rtCount = rt->route_node.size();
                for(int j = 0; j < rtCount; ++j)
                {
                        fout << rt->route_node[j] << ' ';
                }
                fout << rt->consumeID << ' ' << rt->band << endl;
        }
        fout.close();
}

void filter_answer()
{
        std::vector<struct Route *>::iterator ite;
        int ratio[MAX_NODE];
        
        memset(ratio, 0, sizeof(ratio));
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                if((*ite)->len == 1)
                {
                        ratio[(*ite)->serverID] += 2;
                }
                else
                {
                        ratio[(*ite)->serverID] ++;
                }
        }

        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                while(ite != ansVec.end() && ratio[(*ite)->serverID] == 1)
                {
                        back_map(ite);
                        delete (*ite);
                        ansVec.erase(ite);
                        ite = ansVec.begin();
                }
                if(ite == ansVec.end())
                        break;
        }
        //cout << "Filter answer Done!" << endl;
}

void find_answer(int &tern)
{
        struct Route *rt;
        int serverID, endID;
        bool f = 1;
        int tt;
        //float s = 1.5;
        while( !csMap.empty() && f)
        {
                caculate_score();
                f = 0;  tt = 5;
                while(tt > 0 && !f)
                {
                        tt--;
                        serverID = find_server(tern);
                        while( !csMap.empty() && (find_route(serverID, endID, tern) > 0) )
                        {
                                f = 1;
                                rt = new struct Route;
                                update_ans(serverID, endID, *rt);
                                update_map();
                        }
                }
        }
        filter_answer();  //删除只出现一次的服务器节点（并且该节点不是直连）
        while( !csMap.empty() )
        {
                struct Route *rt = new struct Route;
                last_ans(*rt);
                filter_answer();  //删除只出现一次的服务器节点（并且该节点不是直连）
        }
}

void filter_answer(float &s)
{
        std::vector<struct Route *>::iterator ite;
        float ratio[MAX_NODE];
        float rat;

        //初始化
        for(int i = 0; i < MAX_NODE; ++i)
        {
                ratio[i] = 0;
        }

        //计算每个答案的合理程度
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                if((*ite)->len == 1)
                {
                        rat = 1.1;
                }
                else
                {
                        rat = ((float)(*ite)->band) / ((float)consBand[(*ite)->consumeID]);
                }
                ratio[(*ite)->serverID] += rat;
        }

        //删除未满足要求的答案
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                while(ite != ansVec.end() && ratio[(*ite)->serverID] < s)
                {
                        back_map(ite);
                        delete *ite;
                        ansVec.erase(ite);
                        ite = ansVec.begin();
                }
                if(ite == ansVec.end())
                        break;
        }
        //cout << "Filter answer Done!" << endl;
}

void reback_map(struct Route *rt)
{
        int cu, ne;
        int band;
        cu = rt->serverID;
        band = rt->band;
        
        for(unsigned int i = 1; i < (rt->route_node).size(); ++i)
        {
                ne = (rt->route_node)[i];
                band = band > nodeInfo[cu].links[ne]->band ? nodeInfo[cu].links[ne]->band : band;
                cu = ne;
        }
}

void filter_answer(int serverID)
{
        std::vector<struct Route *>::iterator ite;
        float rat = 0;

        //计算每个答案的合理程度
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                if((*ite)->serverID != serverID)
                        continue;
                if((*ite)->len == 1)
                {
                        rat += 1.1;
                }
                else
                {
                        rat += ((float)(*ite)->band) / ((float)consBand[(*ite)->consumeID]);
                }
        }


        if(rat > 1.2)
        {
                nodeInfo[serverID].score *= 1.1;
                for(unsigned int i = 0; i < ansBack.size(); ++i)
                        delete ansBack[i];
                ansBack.clear();
                return ;
        }

        //删除未满足要求的答案
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                while(ite != ansVec.end() && (*ite)->serverID == serverID)
                {
                        back_map(ite);
                        delete (*ite);
                        ansVec.erase(ite);
                        ite = ansVec.begin();
                }
                if(ite == ansVec.end())
                        break;
        }

        for(ite = ansBack.begin(); ite != ansBack.end(); ++ite)
        {
                ansVec.push_back(*ite);
                //reback_map(*ite);
                update_map();
        }
        ansBack.clear();
        nodeInfo[serverID].score *= 0.95;
        serverVis[serverID] = 0;
        //cout << "Filter answer Done!" << endl;
}

int get_answer_cost()
{
        bool visited[MAX_NODE];
        int cost = 0;
        std::vector<struct Route *>::iterator ite;

        memset(visited, 0, sizeof(visited));
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                if( !visited[(*ite)->serverID] )
                {
                        cost += costServer;
                        visited[(*ite)->serverID] = 1;
                }
                if((*ite)->len == 1)
                {
                        continue;
                }
                else
                {
                        cost += ((*ite)->band * (*ite)->cost);
                }
        }
        return cost;
}

void update_score()
{
        std::vector<struct Route *>::iterator ite;
        float ratio[MAX_NODE];
        float rat;

        //初始化
        for(int i = 0; i < MAX_NODE; ++i)
        {
                ratio[i] = 0;
        }

        //计算每个答案的合理程度
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                
                rat = ((float)(*ite)->band) / ((float)consBand[(*ite)->consumeID]);
                ratio[(*ite)->serverID] += rat;
        }

        for(int i = 0; i < nodeNum; ++i)
        {
                if(ratio[i] > 0.2)
                {
                        nodeInfo[i].score *= (ratio[i] - 0.2);
                }
        }
}

void update_map_score()
{
        std::vector<struct Route *>::iterator ite;
        float ratio[MAX_NODE];
        float rat;

        //初始化
        for(int i = 0; i < MAX_NODE; ++i)
        {
                ratio[i] = 0;
        }

        //计算每个答案的合理程度
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                
                rat = ((float)(*ite)->band) / ((float)consBand[(*ite)->consumeID]);
                ratio[(*ite)->serverID] += rat;
        }

        for(int i = 0; i < nodeNum; ++i)
        {
                if(ratio[i] > 2)
                {
                        nodeMap[i].score += (5 * ratio[i] * ratio[i]);
                }
        }
}

void update_answer()
{
        std::vector<struct Route *>::iterator ite;
        for(ite = lastAns.begin(); ite != lastAns.end(); ++ite)
        {
                delete *ite;
        }
        lastAns.clear();
        for(ite = ansVec.begin(); ite != ansVec.end(); ++ite)
        {
                lastAns.push_back(*ite);
        }
        ansVec.clear();
}

 void init_lastAns()
 {
         struct Route *rt;
         for(int i = 0; i < consumeNum; ++i)
         {
                 rt = new struct Route;
                 rt -> len = 1;
                 rt -> band = consBand[i];
                 rt -> cost = 0;
                 rt -> consumeID = i;
                 rt -> serverID = consNode[i];
                 (rt -> route_node).push_back(consNode[i]);
                 lastAns.push_back(rt);
         }
         totalCost = costServer * consumeNum;
         cout << "Direct Cost is: " << totalCost << endl;
 }

//你要完成的功能总入口
void deploy_server(char * topo[MAX_EDGE_NUM], int line_num,char * filename)
{
        struct timeval start_t, end_t;
        long dis = 0;
        float s = 1.3;
        struct Route *rt;
        int serverID, endID;
        int tt = 0;
        gettimeofday(&start_t, NULL);
        srand(unsigned(start_t.tv_sec));
        read_data(topo, line_num);  
        get_info();
        caculate_score();   
        while( !csMap.empty() && dis < 86)
        {        
                tt = (tt + 1) % 501;
                serverID = find_server(tt);
                while( !csMap.empty() && (find_route(serverID, endID, tt) > 0) )
                {
                        rt = new struct Route;
                        update_ans(serverID, endID, *rt);
                        update_map();
                }
                filter_answer(serverID);
                if(tt == 500)
                {
                        filter_answer(s);
                        for(int i = 0; i < nodeNum; ++i)
                                nodeInfo[i].score += 10;
                        memset(serverVis, 0, sizeof(serverVis));
                        for(unsigned int i = 0; i < ansVec.size(); ++i)
                                serverVis[ansVec[i]->serverID] = 1;
                }
                gettimeofday(&end_t, NULL);
                dis = end_t.tv_sec - start_t.tv_sec;
        }
        s = 1.05;
        filter_answer(s);  //删除只出现一次的服务器节点（并且该节点不是直连）
        while( !csMap.empty() )
        {
                rt = new struct Route;
                last_ans(*rt);
                filter_answer(s);  //删除只出现一次的服务器节点（并且该节点不是直连）
        }
        cout << "Cost Time is: " << dis << endl;
        cout << "Minimal Cost is: " << get_answer_cost() << endl;
        update_answer();
        print_ans(filename);
}
